package com.sicheng.蓝桥.练习题.dp.二维费用的背包问题;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/9 23:48
 */
public class 不少于问题 {
    /**
     * 一共有 k 种 物品，对于第 i 种物品，第一维 费用 是 v1i，第二维 费用 是 v2i，价值 是 wi
     * 每个物品只能 被选一次
     * <p>
     * 求一个 选择方案，使得第一维费用 不少于 n，第二维费用 不少于 m 且 总价值最小
     */

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int v = scanner.nextInt();
        int m = scanner.nextInt();

        int[][] dp = new int[v + 1][m + 1];
        int[][] bags = new int[n][3];
        for (int i = 0; i < n; i++) {
            bags[i][0] = scanner.nextInt();//v
            bags[i][1] = scanner.nextInt();//m
            bags[i][2] = scanner.nextInt();//w
        }

        for (int[] arr : dp) {
            Arrays.fill(arr, Integer.MAX_VALUE >> 1);
        }
        //求最小值要把除初始状态以外的所有状态初始化为+∞
        dp[0][0] = 0;

        for (int i = 0; i < n; i++) {
            for (int j = v; j >= 0; j--) {
                for (int k = m; k >= 0; k--) {
                    //这里我们把所有j,k小于0的初始状态都合并到dp[0][0]中来转移,也就是下面的max操作
                    dp[j][k] = Math.min(dp[j][k], dp[Math.max(j - bags[i][0], 0)][Math.max(k - bags[i][1], 0)] + bags[i][2]);
                }
            }
        }
    }
}
